package queue

import (
	"context"
	"errors"
	"sync/atomic"
	"unsafe"
)

// 用链表实现的无锁并发队列
// 用原子操作复杂类型对象，只能用 unsafe.Pointer
type ConcurrentBlockQueueV4[T any] struct {
	head unsafe.Pointer
	tail unsafe.Pointer
}

var (
	ErrEmptyQueue = errors.New("队列为空")
)

func NewConcurrentBlockQueueV4[T any]() *ConcurrentBlockQueueV4[T] {
	head := &node[T]{}
	// 辅助节点，不存数据
	ptr := unsafe.Pointer(head)
	// head、tail 必须都指向辅助节点，才能连成一条链
	return &ConcurrentBlockQueueV4[T]{
		head: ptr,
		tail: ptr,
	}
}

func (c *ConcurrentBlockQueueV4[T]) EnQueue(ctx context.Context, data T) error {
	newNode := &node[T]{
		val: data,
	}
	for {
		if ctx.Err() != nil {
			return ctx.Err()
		}
		tail := atomic.LoadPointer(&c.tail)
		if atomic.CompareAndSwapPointer(&c.tail, tail, unsafe.Pointer(newNode)) { // 先调整尾指针指向新节点
			atomic.StorePointer(&((*node[T])(tail)).next, unsafe.Pointer(newNode)) // 再让新节点入队
			return nil
		}
	}
}
func (c *ConcurrentBlockQueueV4[T]) DeQueue(ctx context.Context) (T, error) {
	for {
		if ctx.Err() != nil {
			var t T
			return t, ctx.Err()
		}
		head := atomic.LoadPointer(&c.head)
		tail := atomic.LoadPointer(&c.tail)
		// 判断队列是否为空
		if head == tail {
			var t T
			return t, ErrEmptyQueue
		}
		// c.head 不存数据，数据在 c.head.next，
		nex := atomic.LoadPointer(&(((*node[T])(c.head)).next))
		// head != tail 并且 head.next == nil，说名有另一个并行线程正在入队，
		// 已调整尾指针指向新节点，但新节点还未入队，这里就跳过，等待它入队完成
		if nex == nil {
			continue
		}
		if atomic.CompareAndSwapPointer(&c.head, head, nex) {
			return (*node[T])(nex).val, nil
		}
	}
}
func (c *ConcurrentBlockQueueV4[T]) IsFull() bool {
	// 不准确，无法实现
	panic("implement me")
}
func (c *ConcurrentBlockQueueV4[T]) IsEmpty() bool {
	// 不准确，无法实现
	panic("implement me")
}
func (c *ConcurrentBlockQueueV4[T]) Len() uint64 {
	// 不准确，无法实现
	panic("implement me")
}

type node[T any] struct {
	next unsafe.Pointer
	val  T
}
